package data_structures_and_algorithms.super_base;

/**
 * @ClassName Array_Prefix_Sum
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/24 13:57
 */
public class Array_Prefix_Sum {

    public static void main(String[] args) {
        int[] nums = new int[]{1,4,2,6,54,7,2};
        System.out.println(getPrefixSum1(nums, 2,5));
        System.out.println(getPrefixSum2(nums, 2,5));
    }

    // 构建二维数组
    public static int getPrefixSum1(int[] nums, int left, int right){
        // 以left为起点 right为终点的数字之和
        int[][] numSum = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (i == j)
                    numSum[i][j] = nums[j];
                else {
                    numSum[i][j] = numSum[i][j - 1] + nums[j];
                }
            }
        }

        return numSum[left][right];
    }

    // 构建一维数组
    public static int getPrefixSum2(int[] nums, int left, int right){
        // 以下标为0作为起点 right为终点的数字之和
        int[] sum = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0){
                sum[i] = nums[i];
            }else {
                sum[i] = sum[i - 1] + nums[i];
            }
        }

        return left == 0?sum[right] : sum[right] - sum[left - 1];
    }
}
